package com.interview.javabase.algorithm;

import javax.swing.plaf.synth.SynthOptionPaneUI;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * @author: zsg
 * @description:
 * @date: 2019/8/24 12:18
 * @modified:
 */
public class PolandNotation {

    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";
        Stack<String> transformation = transformation(expression);
        List<String> list = transformation.subList(0, transformation.size());

        Stack<String> newStack = new Stack<>();
        list.forEach(item -> {
            if (item.matches("\\d+")) {
                newStack.push(item);
            } else {
                int result = cal(Integer.valueOf(newStack.pop()), Integer.valueOf(newStack.pop()), item);
                newStack.push(String.valueOf(result));
            }
        });

        System.out.println(newStack.pop());
    }

    /**
     * 中缀转后缀
     *
     * @param expression
     * @return
     */
    private static Stack<String> transformation(String expression) {
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
        int index = 0;
        List<String> list = new ArrayList();
        while (true) {
            char ch = expression.substring(index, index + 1).charAt(0);
            list.add(String.valueOf(ch));
            index++;
            if (index == expression.length()) {
                break;
            }
        }

        System.out.println(list);

        list.forEach(item -> {
            if (isOperation(item)) {

                // 当stack1不为空且当前的符号的优先级小于等于栈顶的优先级的则需要弹出并且压入到stack2栈中 继续与栈顶比较
                while (!stack1.empty() && priority(item) <= priority((String) stack1.peek())) {
                    stack2.push(stack1.pop());
                }

                stack1.push(item);
            } else if (item.equals("(")) {
                stack1.push(item);
            } else if (item.equals(")")) {
                stack2.push(stack1.pop());
                stack1.pop();
            } else {
                stack2.push(item);
            }
        });

        stack2.push(stack1.pop());
        System.out.println(stack2.toString());
        return stack2;
    }

    /**
     * 计算
     *
     * @param value1
     * @param value2
     * @param ch
     * @return
     */
    public static int cal(int value1, int value2, String ch) {
        int result;
        switch (ch) {
            case "*":
                result = value2 * value1;
                break;
            case "/":
                result = value2 / value1;
                break;
            case "+":
                result = value2 + value1;
                break;
            case "-":
                result = value2 - value1;
                break;
            default:
                result = 0;
        }

        return result;
    }

    /**
     * 是否为操作符
     *
     * @param ch
     * @return
     */
    private static boolean isOperation(String ch) {
        return ch.equals("*") || ch.equals("/") || ch.equals("-") || ch.equals("+");
    }

    /**
     * 优先级
     *
     * @param ch
     * @return
     */
    public static int priority(String ch) {
        if (ch.equals("*") || ch.equals("/")) {
            return 2;
        } else if (ch.equals("-") || ch.equals("+")) {
            return 1;
        } else {
            return -1;
        }
    }
}
